package com.tgy.algorithm.base;

public class _把链表划分成左边_中间_右边_01 {

    public static Node generalNode(int[] nums) {

        if (nums == null || nums.length == 0) {
            return null;
        }
        Node header = new Node(nums[0], null);
        Node cur = header;
        for (int i = 1; i < nums.length; i++) {
            Node node = new Node(nums[i], null);
            cur.next = node;
            cur = node;
        }
        return header;
    }

    public static void printNode(Node node) {
        while (node != null) {
            System.out.print(node.num + " ");
            node = node.next;
        }

        System.out.println();
    }

    public static Node classifyNode(Node header,  int target) {

        if (header == null || header.next == null) {
            return header;
        }

        Node ltHeadNode = null;
        Node ltTailNode = null;
        Node eqHeadNode = null;
        Node eqTailNode = null;
        Node gtHeadNode = null;
        Node gtTailNode = null;

        Node node = header;

        while (node != null) {

            if (node.num < target) {
                if (ltHeadNode == null) {
                    ltHeadNode = node;
                    ltTailNode = node;
                }else {
                    ltTailNode.next = node;
                    ltTailNode = node;
                }
            }else if(node.num == target) {
                if (eqHeadNode == null) {
                    eqHeadNode = node;
                    eqTailNode = node;
                }else {
                    eqTailNode.next = node;
                    eqTailNode = node;
                }
            }else {
                if (gtHeadNode == null) {
                    gtHeadNode = node;
                    gtTailNode = node;
                }else {
                    gtTailNode.next = node;
                    gtTailNode = node;
                }
            }
            node = node.next;
        }

        if (ltTailNode != null) {
            ltTailNode.next = null;
        }

        if (eqTailNode != null) {
            eqTailNode.next = null;
        }

        if (gtTailNode != null) {
            gtTailNode.next = null;
        }

        Node lastNode = null;
        lastNode = ltHeadNode != null ? ltHeadNode : (eqHeadNode != null ? eqHeadNode : gtHeadNode);

        if (ltTailNode != null ) {
            if (eqHeadNode != null) {
                ltTailNode.next = eqHeadNode;
                eqTailNode.next = gtHeadNode;
            }else {
                ltTailNode.next = gtHeadNode;
            }
        }

        if (eqTailNode != null) {
            if (gtHeadNode != null) {
                eqTailNode.next = gtHeadNode;
            }
        }

        return lastNode;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,2,4,4,3,1};
        Node node = generalNode(nums);
        printNode(node);
        Node classifNd = classifyNode(node, 2);
        printNode(classifNd);
    }
}
